Algorithims Heap Project

Hannah Butsko, Emma Horton, Arianne Pozzi, Matthew Wilcox

Purpose

  • Process Student Applications
  • Prioritize them based on various criteria
  • Make admission offers to most qualified/preferred candidates

Max Heap Implemenation

def max_heap(lst, n, i):
    largest = i
    # Calculating positions of left and right children
    left = i * 2 + 1
    right = i * 2 + 2

    # Comparing the largest value to the left child
    if left < n and lst[largest] < lst[left]:
        largest = left

    # Comparing the largest value to the right child
    if right < n and lst[largest] < lst[right]:
        largest = right

    # Checking if largest index has been changed
    # No need to swap elements or call function recursively if largest element was not changed
    if largest != i:
        # Swapping the values of the parent with the largest element
        lst[largest], lst[i] = lst[i], lst[largest]

        # Call function recursively to check children values
        max_heap(lst, n, largest)

Add a new value to the heap

def add_heap(lst, value):
    lst.append(value)  # Add the new value to the end of the heap
    idx = len(lst) - 1  # Get the index of the newly added element

    # Moving the newly added element up the tree as long as it's greater
    # than its parent, maintaining the max heap property
    while idx > 0:
        parent_index = (idx - 1) // 2
        if lst[idx] > lst[parent_index]:
            lst[idx], lst[parent_index] = lst[parent_index], lst[idx]
            idx = parent_index
        else:
            break

Pop max heap implementation

def pop_max_heap(lst):
    # Checking if list is empty
    if not list:
        return "The array is empty"

    # Checking if there is only one element in the list
    if len(lst) == 1:
        return lst.pop()

    # Maximum element
    max_elem = lst[0]
    # Last element
    last = lst.pop()

    if lst:
        # Moving the last element to the root position
        lst[0] = last
        index = 0
        n = len(lst)

        # Restore the tree by bringing down the element
        max_heap(lst, index, n)

    # Returning the maximum element that was removed
    return max_elem

Prioritizing each student

def priority(payload, idx):
    lst_priority = [
        1 if payload["student_type"] == "Graduate" else 0,
        1 if payload["computer_science"] is True else 0,
        1 if payload["math"] is True else 0,
        payload["year"],  # Closer students are graduating - higher the priority
        -payload["orientation_day"],  # Reversing the orientation day value to give priority to students that register earlier
        idx  # Unique identifier of each student
    ]

    return lst_priority

Processing each student and admitting by priority criteria

def process_admissions(payload):
    lst = []
    admitted_students = []  # Initialize a list for admitted students

    # Enumerating through student requests and prioritizing them
    for idx, student in enumerate(payload):
        priority_student = priority(student, idx)
        add_heap(lst, priority_student)  # Adding every priority to our max heap

    # Admitting students up to a limit 25 based on max heap priorities
    while len(admitted_students) < 25 and len(lst) > 0:
        _, computer_science, math, year, orientation_day, idx = pop_max_heap(lst)
        admitted_students.append(idx)

    return admitted_students

Making offers to admitted students if places become available

def make_offers(payload, admitted_students, dropouts):
    offers = []

    # Checking for admitted students who haven't dropped the class
    for idx, request in enumerate(payload):
        if idx in admitted_students and idx not in dropouts:
            offers.append(request)

    # Filling empty spots with the most qualified students
    while len(offers) < 25:
        # Checking for the next most qualified student who hasn't been previously admitted
        next_student = None
        for index, request in enumerate(payload):
            if index not in admitted_students and index not in dropouts:
                if next_student is None or priority(request, index) > priority(next_student, index):
                    next_student = request

        # If no more qualified students are available, break the loop
        if next_student is None:
            break

        # Marking the student as admitted and add them to the offers list
        admitted_students.append(payload.index(next_student))
        offers.append(next_student)

    return offers

Function that organizes student payload into a dictionary

We organized each student into a dictionary to use within the functions to retain all of the students data while assigning a priority

def student_data(name, student_type, computer_science, math, year, orientation_day, email, street, city, state, zip_code):
    return {"name": name,
            "student_type": student_type,
            "computer_science": computer_science,
            "math": math,
            "year": year,
            "orientation_day": orientation_day,
            "email": email,
            "Street Address": street,
            "City": city,
            "State": state,
            "ZIP Code": zip_code}

Make a random fake data set of size n

Using the faker package we built a function to create random students to populate our school to test our functions in createing priority queues.

def random_student_admission(size=40):
    # Initialize Faker
    fake = Faker()
    # Create list of student_data dicts
    student_list = []
    for individual in range(0, size):
        name = fake.name()
        student_type = np.random.choice(['Undergraduate', 'Graduate', 'Auditor'])
        computer_science = np.random.choice([True, False])
        math = np.random.choice([True, False])
        year = np.random.randint(0, 5)
        orientation = np.random.randint(1, 6)
        fake_email = fake.free_email()
        fake_address = fake.street_address()
        fake_city = fake.city()
        fake_state = fake.state()
        fake_zip = fake.postcode()
        student_list.append(
            student_data(name, student_type, computer_science, math, year, orientation, fake_email, fake_address, fake_city, fake_state, fake_zip))

    return student_list

Create Admited Sutdents List

We first create a list of admited students. We select the size of our class and generate a random class of that size. In this case we do 38/

Create Admited Sutdents List

We then process them through admissions leaving us with a table of admitted students.

                    name   student_type  computer_science   math  year  \
0         Michael Duncan        Auditor              True  False     0   
1         Jessica Thomas        Auditor              True  False     4   
2            Julie White  Undergraduate             False  False     3   
3       Melissa Pitts MD  Undergraduate              True   True     0   
4          Timothy Smith        Auditor              True   True     0   
5    Autumn Gutierrez MD  Undergraduate              True   True     3   
6        Joseph Williams        Auditor              True  False     2   
7           Kayla Benson        Auditor             False  False     1   
8       Michael Thompson        Auditor              True   True     2   
9         Frank Hobbs MD  Undergraduate             False  False     3   
10     William Dominguez  Undergraduate             False  False     4   
11           Todd Lozano        Auditor              True   True     1   
12           James Myers  Undergraduate              True  False     1   
13           James Curry  Undergraduate             False   True     1   
14        Vanessa Miller  Undergraduate              True  False     1   
15          Harry Phelps  Undergraduate              True  False     2   
16        Matthew Morrow  Undergraduate              True   True     1   
17            Tina Leach        Auditor              True   True     2   
18        Brian Stephens       Graduate              True  False     1   
19      Collin Mcpherson       Graduate             False   True     4   
20       Jeffrey Flowers        Auditor              True   True     3   
21         Andrew Harris  Undergraduate             False   True     0   
22  Patricia Collins DDS  Undergraduate              True  False     2   
23         Deborah Lopez  Undergraduate             False   True     1   
24         Jasmine Brown        Auditor              True   True     1   

    orientation_day                        email  \
0                 1            eturner@yahoo.com   
1                 5          michael64@yahoo.com   
2                 3             jjones@yahoo.com   
3                 5           westjudy@yahoo.com   
4                 5   hickschristopher@yahoo.com   
5                 4           sjackson@gmail.com   
6                 3       rodneyglover@gmail.com   
7                 2        jamesteresa@yahoo.com   
8                 4       smithmichele@yahoo.com   
9                 5            karen98@gmail.com   
10                4      hernandezjohn@yahoo.com   
11                4          qbowman@hotmail.com   
12                2             qparks@yahoo.com   
13                2    alexandermiller@gmail.com   
14                1        blairbrandy@yahoo.com   
15                4         tinaortega@yahoo.com   
16                5   lindseymcconnell@gmail.com   
17                5     raymondquinn@hotmail.com   
18                2           howens@hotmail.com   
19                1  williamselizabeth@gmail.com   
20                1         kaylacasey@yahoo.com   
21                2      ashleyhouston@yahoo.com   
22                3     edwardseduardo@yahoo.com   
23                2    williamsbryan@hotmail.com   
24                4     zacharyclark@hotmail.com   

                    Street Address                 City           State  \
0              23491 Jessica Trace     Lake Cherylmouth      New Jersey   
1            138 Sandra Expressway          Kennethstad      New Jersey   
2     19110 Marcus Canyon Apt. 390          New William         Indiana   
3   96466 Gregory Radial Suite 925           Millerview           Idaho   
4                6644 Lewis Bypass  West Natalieborough         Arizona   
5         506 Juan Parks Suite 558            Kevinfurt        Kentucky   
6              6507 Camacho Greens        Cassandraport     Mississippi   
7        1343 Daisy Ville Apt. 487       East Jamesland        Nebraska   
8       37337 Watson Burg Apt. 410          Zacharyberg   West Virginia   
9           74273 Samantha Mission            Tinamouth      California   
10     60809 Curtis Lake Suite 803            Youngland  North Carolina   
11             42549 Wanda Village           Grimesview         Montana   
12              48608 Jones Estate    South Marissaport   New Hampshire   
13      899 Hill Passage Suite 465          Port Nicole         Florida   
14              2704 Austin Square          New William    North Dakota   
15      6356 Lane Mission Apt. 699          Monicashire         Wyoming   
16       0400 Rick Mount Suite 453           Daltonland  North Carolina   
17               89375 Perez Falls          Matthewview   New Hampshire   
18            56720 Schmidt Fields           Crosbystad       Tennessee   
19     04263 Harvey Fork Suite 399         West Michael          Kansas   
20     26308 David Route Suite 316      New Nathanhaven       Louisiana   
21     979 Noah Causeway Suite 639          Kennedyfort         Vermont   
22                8873 Graham Fall           Wolfehaven  North Carolina   
23         175 Lynch Fort Apt. 265             Ortizton         Alabama   
24              785 Lewis Motorway        Port Jennifer  South Carolina   

   ZIP Code  
0     45803  
1     18909  
2     39284  
3     63974  
4     82823  
5     29256  
6     54937  
7     42775  
8     84134  
9     52366  
10    06302  
11    82295  
12    58256  
13    14365  
14    74771  
15    23211  
16    02388  
17    12148  
18    07100  
19    30133  
20    00544  
21    83776  
22    37556  
23    62939  
24    90873  

Simulating dropouts

We are now goint to simulate two students, {python} admitted_students[3]

dropouts = [admitted_students[3], admitted_students[17]]

Making offers if places become available

This is now the final class after we had 2 dropouts.

                    name   student_type  computer_science   math  year  \
0         Michael Duncan        Auditor              True  False     0   
1         Jessica Thomas        Auditor              True  False     4   
2            Julie White  Undergraduate             False  False     3   
3       Melissa Pitts MD  Undergraduate              True   True     0   
4    Autumn Gutierrez MD  Undergraduate              True   True     3   
5           Kayla Benson        Auditor             False  False     1   
6       Michael Thompson        Auditor              True   True     2   
7         Frank Hobbs MD  Undergraduate             False  False     3   
8      William Dominguez  Undergraduate             False  False     4   
9            Todd Lozano        Auditor              True   True     1   
10           James Myers  Undergraduate              True  False     1   
11           James Curry  Undergraduate             False   True     1   
12        Vanessa Miller  Undergraduate              True  False     1   
13          Harry Phelps  Undergraduate              True  False     2   
14        Matthew Morrow  Undergraduate              True   True     1   
15            Tina Leach        Auditor              True   True     2   
16        Brian Stephens       Graduate              True  False     1   
17      Collin Mcpherson       Graduate             False   True     4   
18       Jeffrey Flowers        Auditor              True   True     3   
19         Andrew Harris  Undergraduate             False   True     0   
20  Patricia Collins DDS  Undergraduate              True  False     2   
21         Deborah Lopez  Undergraduate             False   True     1   
22         Jasmine Brown        Auditor              True   True     1   
23        Damon Anderson       Graduate             False  False     3   
24          Kerri Oliver       Graduate              True  False     2   

    orientation_day                        email  \
0                 1            eturner@yahoo.com   
1                 5          michael64@yahoo.com   
2                 3             jjones@yahoo.com   
3                 5           westjudy@yahoo.com   
4                 4           sjackson@gmail.com   
5                 2        jamesteresa@yahoo.com   
6                 4       smithmichele@yahoo.com   
7                 5            karen98@gmail.com   
8                 4      hernandezjohn@yahoo.com   
9                 4          qbowman@hotmail.com   
10                2             qparks@yahoo.com   
11                2    alexandermiller@gmail.com   
12                1        blairbrandy@yahoo.com   
13                4         tinaortega@yahoo.com   
14                5   lindseymcconnell@gmail.com   
15                5     raymondquinn@hotmail.com   
16                2           howens@hotmail.com   
17                1  williamselizabeth@gmail.com   
18                1         kaylacasey@yahoo.com   
19                2      ashleyhouston@yahoo.com   
20                3     edwardseduardo@yahoo.com   
21                2    williamsbryan@hotmail.com   
22                4     zacharyclark@hotmail.com   
23                2          cynthia61@yahoo.com   
24                3         hannah95@hotmail.com   

                    Street Address               City           State ZIP Code  
0              23491 Jessica Trace   Lake Cherylmouth      New Jersey    45803  
1            138 Sandra Expressway        Kennethstad      New Jersey    18909  
2     19110 Marcus Canyon Apt. 390        New William         Indiana    39284  
3   96466 Gregory Radial Suite 925         Millerview           Idaho    63974  
4         506 Juan Parks Suite 558          Kevinfurt        Kentucky    29256  
5        1343 Daisy Ville Apt. 487     East Jamesland        Nebraska    42775  
6       37337 Watson Burg Apt. 410        Zacharyberg   West Virginia    84134  
7           74273 Samantha Mission          Tinamouth      California    52366  
8      60809 Curtis Lake Suite 803          Youngland  North Carolina    06302  
9              42549 Wanda Village         Grimesview         Montana    82295  
10              48608 Jones Estate  South Marissaport   New Hampshire    58256  
11      899 Hill Passage Suite 465        Port Nicole         Florida    14365  
12              2704 Austin Square        New William    North Dakota    74771  
13      6356 Lane Mission Apt. 699        Monicashire         Wyoming    23211  
14       0400 Rick Mount Suite 453         Daltonland  North Carolina    02388  
15               89375 Perez Falls        Matthewview   New Hampshire    12148  
16            56720 Schmidt Fields         Crosbystad       Tennessee    07100  
17     04263 Harvey Fork Suite 399       West Michael          Kansas    30133  
18     26308 David Route Suite 316    New Nathanhaven       Louisiana    00544  
19     979 Noah Causeway Suite 639        Kennedyfort         Vermont    83776  
20                8873 Graham Fall         Wolfehaven  North Carolina    37556  
21         175 Lynch Fort Apt. 265           Ortizton         Alabama    62939  
22              785 Lewis Motorway      Port Jennifer  South Carolina    90873  
23                 428 Darren View        Brandonport      California    73720  
24             8345 Krystal Island    West Ashleystad         Indiana    05262  

Power BI Implementation

Power Bi - Data Model

Power Bi - Not Admitted Students

Power Bi - Admitted Students

Power Bi - Acceptance email